package com.example.demo.程序员面试金典;

import com.example.demo.StopWatchTemplate;
import java.util.ArrayList;
import java.util.List;

/**
 * @description: TODO
 * @author: zhangzc
 * @modified By: zhangzc
 * @date: Created in 2022/9/8 15:20
 * @version:v1.0
 */
public class 括号 {

	// todo todo
	//深度优先搜索 DFS。
	public static List<String> generateParenthesis(int n) {
		List<String> ans = new ArrayList<>();
		dfs(0, 0, n, "", ans);
		return ans;
	}

	private static void dfs(int left, int right, int n, String t, List<String> ans) {
		if (left == n && right == n) {
			ans.add(t);
			return;
		}
		if (left < n) {
			dfs(left + 1, right, n, t + "(", ans);
		}
		if (right < left) {
			dfs(left, right + 1, n, t + ")", ans);
		}
	}

	public static void main(String[] args) {
		System.out.println(StopWatchTemplate.doSupplier(() -> generateParenthesis(3)));
	}

	class Solution {

		List<String> res = new ArrayList<>();

		public List<String> generateParenthesis(int n) {
			dfs("", 0, 0, n);
			return res;

		}

		private void dfs(String paths, int left, int right, int n) {
			if (left > n || right > left) {
				return;
			}
			if (paths.length() == 2 * n) {
				res.add(new String(paths));
				return;
			}
			dfs(paths + "(", left + 1, right, n);
			dfs(paths + ")", left, right + 1, n);
		}
	}

	static class Solution2 {

		public static void main(String[] args) {
			System.out.println(StopWatchTemplate.doSupplier(() -> generateParenthesis(3)));
		}

		static List<String> res = new ArrayList<String>();

		public static List<String> generateParenthesis(int n) {
			String currentStr = "";
			int left = 0;
			int right = 0;
			dfs(n, currentStr, left, right);
			return res;
		}

		public static void dfs(int n, String currentStr, int left, int right) {
			// 终止条件
			if (currentStr.length() == 2 * n) {
				res.add(currentStr);
				return;
			}
			// 如果该位置的left<n 则可添加左括号
			if (left < n) {
				dfs(n, currentStr + "(", left + 1, right);
			}
			// 如果该位置的右括号数目小于左括号 则可添加右括号
			if (right < left) {
				dfs(n, currentStr + ")", left, right + 1);
			}
		}
	}


}
